Distanță Manhattan

Distanța Manhattan este o distanță specifică într-o geometrie în care funcția obișnuită de distanță (metrică) din geometria euclidiană este înlocuită cu o nouă metrică în care distanța dintre două puncte este suma diferențelor absolute ale coordonatelor carteziene.^[1] Metrica Manhattan este cunoscută și ca distanță L₁, distanță L¹ sau normă $\ell _{1}$ . Denumirea distanței provine de la trama stradală din Manhattan, unde traseele taximetrelor pot avea aceeași lungime pentru diferite căi.

Geometria a fost utilizată în analiza de regresie încă din secolul al XVIII-lea, iar astăzi este adesea denumită LASSO. Interpretarea geometrică datează din geometria neeuclidiană a secolului al XIX-lea și se datorează lui Hermann Minkowski.

Definiția formală

Distanța Manhattan, $d_{1}$ , dintre doi vectori $\mathbf {p} ,\mathbf {q}$ într-un spațiu vectorial real n-dimensional cu un sistem de coordonate carteziene, este suma lungimilor proiecțiilor segmentelor dintre puncte pe axele de coordonate. Formal,

d_{1}(\mathbf {p} ,\mathbf {q} )=\|\mathbf {p} -\mathbf {q} \|_{1}=\sum _{i=1}^{n}|p_{i}-q_{i}|,

unde $(\mathbf {p} ,\mathbf {q} )$ sunt vectori euclidieni

\mathbf {p} =(p_{1},p_{2},\dots ,p_{n}){\text{ si }}\mathbf {q} =(q_{1},q_{2},\dots ,q_{n})\,

De exemplu, în plan, distanța Manhattan dintre $(p_{1},p_{2})$ and $(q_{1},q_{2})$ este $|p_{1}-q_{1}|+|p_{2}-q_{2}|.$

Proprietăți

Distanța Manhattan depinde de rotația sistemului de coordonate, dar nu depinde de reflexia față de o axă de coordonate sau de translația acesteia. Geometria Manhattan satisface toate axiomele Hilbert (o formalizare a geometriei euclidiene), cu excepția axiomei LUL (latură–unghi–latură), ca două triunghiuri cu laturi de lungime egală și unghiul dintre ele identic nu sunt de obicei congruente decât dacă elementele menționate se întâmplă să fie paralele.

Cercuri

Un cerc este o mulțime de puncte situate la o distanță fixă, numită rază, de un punct numit centru. În geometria Manhattan distanța este determinată de o metrică diferită de cea din geometria euclidiană, iar cercurile au altă formă. Cercurile Manhattan sunt pătrate cu laturile orientate la un unghi de 45° față de axele de coordonate. Imaginea alăturată arată de ce acest lucru este adevărat, arătând în roșu mulțimea tuturor punctelor de la aceeași distanță față de un centru, marcat cu albastru. Pe măsură ce dimensiunea cvartalelor din oraș se diminuează, punctele devin mai numeroase și devin un pătrat rotit într-o geometrie Manhattan continuă. În timp ce fiecare latură a acestui pătrat ar avea în metrica euclidiană lungimea ${\sqrt {2}}r$ unde r este raza cercului, lungimea sa în geometria Manhattan este 2r. Astfel, lungimea circumferinței cercului este 8r. Astfel, în această geometrie valoarea analogului geometric al $\pi$ este 4. Formula cercului unitate în geometria Manhattan este în coordonate carteziene $|x|+|y|=1$ iar în coordonate polare

r={\frac {1}{|\sin \theta |+|\cos \theta |}}

Un cerc de rază 1 (folosind această distanță) este vecinătatea von Neumann a centrului său.

Un cerc de rază r pentru distanța Cebîșev (metrica L_∞) din plan este tot un pătrat, cu raza 2r, paralel cu axele de coordonate, astfel distanța Cebîșev din plan poate fi considerată echivalentă cu distanța Manhattan rotită și scalată. totuși, această echivalență între metricile L₁ și L_∞ nu se generalizează pentru dimensiuni superioare.

Ori de câte ori fiecare pereche dintr-o colecție de astfel de cercuri are o intersecție neocupată, există un punct de intersecție pentru întreaga colecție; prin urmare, distanța Manhattan formează un spațiu metric injectiv.

Aplicații

Distanțele la șah

În șah, distanța dintre pătratele de pe tabla de șah pentru turnuri este distanța Manhattan. Pentru regi și dame este distanța Cebîșev. Pentru nebuni este distanța Manhattan (între pătrate de aceeași culoare) pe tabla de șah rotită cu 45°, adică cu diagonalele sale ca axe de coordonate. Pentru a ajunge de la un pătrat la altul, numai regii necesită numărul de mișcări egale cu distanța lor respectivă; turnurile, damele și nebunii necesită una sau două mutări (pe o tablă goală și presupunând că mutarea este posibilă în cazul nebunului).

Achiziția comprimată

În rezolvarea unui sistem nedeterminat de ecuații liniare, regularizarea vectorului parametru este exprimată în termeni de geometrie Manhattan, ca $\ell _{1}$ -normă.^[2] Această abordare apare în cadrul recuperării semnalului numită achiziție comprimată.

Diferențele distribuțiilor de frecvență

Geometria Manhattan poate fi utilizată pentru a evalua diferențele în distribuțiile discrete de frecvență. De exemplu, în matisarea ARN distribuțiile poziționale ale hexamerilor, care prezintă probabilitatea ca fiecare hexamer să apară la fiecare nucleotidă dată lângă un loc de îmbinare, poate fi comparat cu distanța L1. Fiecare distribuție de poziție poate fi reprezentată ca un vector în care fiecare intrare reprezintă probabilitatea ca hexamerul să înceapă de la un anumit nucleotid. O distanță mare L1 între cei doi vectori indică o diferență semnificativă în natura distribuțiilor, în timp ce o distanță mică denotă distribuții în formă similară. Acest lucru este echivalent cu măsurarea ariei dintre cele două curbe de distribuție, deoarece aria fiecărui segment este diferența absolută dintre probabilitățile celor două curbe în acel moment. Când sunt însumate pentru toate segmentele, oferă aceeași măsură ca distanța L1.^[3]

Istoric

Metrica L¹ a fost folosită în analiza de regresie în 1757 de Roger Joseph Boscovich.^[4] Interpretarea geometrică datează de la sfârșitul secolului al XIX-lea și dezvoltarea geometriilor neeuclidiene, în special de Hermann Minkowski. În geometria Manhattan inegalitatea lui Minkowski este un caz particular, utilizat în special în geometria numerelor, (Minkowski 1910). Formalizarea spațiilor L^p se datorează lui (Riesz 1910).

Note

^ en Black, Paul E. „Manhattan distance”. Dictionary of Algorithms and Data Structures. Accesat în 6 octombrie 2019.
^ en Donoho, David L. (23 martie 2006). „For most large underdetermined systems of linear equations the minimal $\ell _{1}$ -norm solution is also the sparsest solution”. Communications on Pure and Applied Mathematics. 59 (6): 797–829. doi:10.1002/cpa.20132.
^ en Lim, Kian Huat; Ferraris, Luciana; Filloux, Madeleine E.; Raphael, Benjamin J.; Fairbrother, William G. (5 iulie 2011). „Using positional distribution to identify splicing elements and predict pre-mRNA processing defects in human genes”. Proceedings of the National Academy of Sciences of the United States of America. 108 (27): 11093–11098. Bibcode:2011PNAS..10811093H. doi:10.1073/pnas.1101135108. PMC 3131313 . PMID 21685335.
^ en Stigler, Stephen M. (1986). The History of Statistics: The Measurement of Uncertainty before 1900. Harvard University Press. ISBN 9780674403406. Accesat în 6 octombrie 2019.

Bibliografie

en Krause, Eugene F. (1987). Taxicab Geometry. Dover. ISBN 978-0-486-25202-5.
de Minkowski, Hermann (1910). Geometrie der Zahlen (în germană). Leipzig and Berlin: R. G. Teubner. JFM 41.0239.03. MR 0249269. Accesat în 6 octombrie 2019.
de Riesz, Frigyes (1910). „Untersuchungen über Systeme integrierbarer Funktionen”. Mathematische Annalen (în germană). 69 (4): 449–497. doi:10.1007/BF01457637. hdl:10338.dmlcz/128558 .

Vezi și

Legături externe

Portal Matematică

en Eric W. Weisstein, Taxicab Metric la MathWorld.
en Malkevitch, Joe (1 octombrie 2007). „Taxi!”. American Mathematical Society. Accesat în 6 octombrie 2019.

[1] Black, Paul E. „Manhattan distance”. Dictionary of Algorithms and Data Structures. Accesat în 6 octombrie 2019.

[2] Donoho, David L. (23 martie 2006). „For most large underdetermined systems of linear equations the minimal $\ell _{1}$ -norm solution is also the sparsest solution”. Communications on Pure and Applied Mathematics. 59 (6): 797–829. doi:10.1002/cpa.20132.

[lim-3] Lim, Kian Huat; Ferraris, Luciana; Filloux, Madeleine E.; Raphael, Benjamin J.; Fairbrother, William G. (5 iulie 2011). „Using positional distribution to identify splicing elements and predict pre-mRNA processing defects in human genes”. Proceedings of the National Academy of Sciences of the United States of America. 108 (27): 11093–11098. Bibcode:2011PNAS..10811093H. doi:10.1073/pnas.1101135108. PMC 3131313 . PMID 21685335.

[Stigler1986-4] Stigler, Stephen M. (1986). The History of Statistics: The Measurement of Uncertainty before 1900. Harvard University Press. ISBN 9780674403406. Accesat în 6 octombrie 2019.

[1]

[2]

[3]

[4]